﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
// 原题连接：https://leetcode.cn/problems/xoh6Oh/description/
/*
题目描述：
给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。



注意：

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1


示例 1：

输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7
示例 2：

输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2
示例 3：

输入：a = 0, b = 1
输出：0
示例 4：

输入：a = 1, b = 1
输出：1


提示:

-231 <= a, b <= 231 - 1
b != 0
*/

// 开始解题：
// 方法——位运算
class Solution {
public:
    int divide(int x, int y) {
        long long a = abs((long long)x);
        long long b = abs((long long)y);
        // 符号
        bool flag = false;
        if ((x < 0 && y > 0) || (x > 0 && y < 0)) {
            flag = true;
        }
        vector<long long> exp; // exp[i]存储的是y * 2^(i + 1)次方
        for (long long i = b; i <= a; i = i + i) {
            exp.push_back(i);
        }
        long long ret = 0;
        for (int i = exp.size() - 1; i >= 0; i--) {
            if (a >= exp[i]) {
                a -= exp[i];
                ret |= 1ll << i; // 这里要使用1ll(也就是long long类型的1来移位，因为有可能移动的不止31位)
            }
        }
        if (flag) {
            ret = -ret;
        }
        if (ret > INT_MAX || ret < INT_MIN) {
            ret = INT_MAX;
        }
        return ret;
    }
};